⟸ pàgina anterior ⟸

Exercici 8 (Tasca 2).

(regular languages, minimization of DFAs)

Minimització de DFAs

1. Un DFA amb estats inaccessibles no pot ser mínim. Quin és el cost de determinar si un DFA té estats inaccessibles?

2. Quin és el cost de l’algorisme de minimització de Moore (amb una implementació raonable)?

3. El mínim DFA que reconeix un llenguatge donat és únic llevat d’isomorfismes. Què es pot dir dels NFAs? En concret, és un NFA de mida mínima únic per un llenguatge donat?